package 刷题10月.剑指offer;
// https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca?tpId=13&tqId=23286&ru=/ta/sql-quick-study&qru=/ta/sql-quick-study/question-ranking
public class JZ15反转链表1002 {

public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
    public class Solution {
        public ListNode ReverseList(ListNode head) {
            ListNode newHead;
            if (head == null || head.next == null) {
                return head;
            }
            newHead = ReverseList(head.next); // head.next 作为剩余部分的头指针
            // head.next 代表新链表的尾，将它的 next 置为 head，就是将 head 加到末尾了。
            head.next.next = head;
            head.next = null;
            return newHead;

        }
    }
    /*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
    public class Solution1 {
        public ListNode ReverseList(ListNode head) {
            // 判断链表为空或长度为1的情况
            if(head == null || head.next == null){
                return head;
            }
            ListNode pre = null; // 当前节点的前一个节点
            ListNode next = null; // 当前节点的下一个节点
            while( head != null){
                next = head.next; // 记录当前节点的下一个节点位置；
                head.next = pre; // 让当前节点指向前一个节点位置，完成反转
                pre = head; // pre 往右走
                head = next;// 当前节点往右继续走
            }
            return pre;
        }
    }
}
